package com.iter.devbox.datastructure;

/**
 * 顺序线性表（顺序链表）
 * 
 * @author Jimly
 */
public class Sqlist {
	
	/**数组中元素个数*/
	private int elementCount;
	
	/**默认数组容量*/
	private static final int DEFAULT_CAPACITY = 10;
	
	/**数组*/
	private Object[] elementData;
	
	/**线性表构造方法，初始化为容量为10的数组*/
	public Sqlist() {
		this.elementData = new Object[DEFAULT_CAPACITY];
	}
	
	/**线性表是否为空*/
	public boolean isEmpty() {
		if (null==elementData || elementData.length==0) {
			return true;
		}
		return false;
	}
	
	/**清空线性表*/
	public void clear() {
		elementCount = 0;
		elementData = null;
	}
	
	/**获取线性表第i个元素*/
	public Object get(int i) {
		if (i >= elementData.length) {
			throw new RuntimeException("数组越界");
		}
		return elementData[i];
	}
	
	/**是否包含给定的元素*/
	public boolean contains(Object o) {
		int index = -1;
		for (int i=0; i<elementData.length; i++) {
			if (o.equals(elementData[i])) {
				index = i;
			}
		}
		if (index >= 0) {
			return true;
		}
		return false;
	}
	
	/**线性表添加一个数据元素*/
	public boolean add (Object object) {
		if (null == elementData) {
			elementData = new Object[DEFAULT_CAPACITY];
			elementData[0] = object;
			elementCount ++;
			return true;
		} else {
			if (elementCount < elementData.length) {
				elementData[elementCount] = object;
				elementCount ++;
			} else {
				Object[] newArry = new Object[elementData.length + elementData.length/2];
				for (int i=0; i<elementData.length; i++) {
					newArry[i] = elementData[i];
				}
				newArry[elementData.length] = object;
				elementCount ++;
			}
		}
		return true;
	}
	
	/**删除线性表第i个元素*/
	public boolean remove (int i) {
		if (i > elementData.length) {
			throw new RuntimeException("数组越界");
		}
		elementData[i] = null;
		elementCount --;
		Object[] newArry = new Object[elementData.length - 1];
		for (int index=0; index<elementData.length; index++) {
			if (index<i) {
				newArry[index] = elementData[index];
			} else if (index>i) {
				newArry[index-1] = elementData[index];
			}
		}
		elementData = newArry;
		return true;
	}
	
	/**线性表的长度*/
	public int size () {
		return elementCount;
	}

	/**main方法测试*/
	public static void main(String[] args) {
		Sqlist sqlist = new Sqlist();
		System.out.println("初始化：" + sqlist.size());
		sqlist.add("1");
		sqlist.add("2");
		sqlist.add("3");
		sqlist.add("4");
		sqlist.add("5");
		System.out.println("元素个数：" + sqlist.size());
		for (int i=0; i<sqlist.size(); i++) {
			System.out.println("遍历：" +sqlist.get(i));
		}
		sqlist.remove(3);
		for (int i=0; i<sqlist.size(); i++) {
			System.out.println("删除一个元素后遍历：" +sqlist.get(i));
		}
		
		System.out.println("是否是空：" + sqlist.isEmpty());
		System.out.println("是否包含指定元素：" + sqlist.contains("5"));
		sqlist.clear();
		System.out.println("清空后size：" + sqlist.size());
		System.out.println("清空后是否为空：" + sqlist.isEmpty());
	}
}
